package com.jzoffer;

import java.time.LocalDateTime;
import java.util.concurrent.TimeUnit;

public class FibonacciArray {
    public static void main(String[] args) throws InterruptedException {
        int n = 40;

        long start1 = System.currentTimeMillis();
        int res1 = Fibonacci(n);
        long end1 = System.currentTimeMillis();
        System.out.println("方法1结果为：" + res1 + ",用时："+(end1 - start1));

        TimeUnit.SECONDS.sleep(3);

        long start2 = System.currentTimeMillis();
        int res2 = Fibonacc2(n);
        long end2 = System.currentTimeMillis();
        System.out.println("方法2结果为：" + res2 + ",用时："+(end2 - start2));

        TimeUnit.SECONDS.sleep(3);

        long start3 = System.currentTimeMillis();
        LocalDateTime now = LocalDateTime.now();
        int res3 = Fibonacc3(n);
        long end3 = System.currentTimeMillis();
        System.out.println("方法3结果为：" + res3 + ",用时："+(end3 - start3));

    }

    public static int Fibonacci(int n){
        if(n <= 1){
            return n;
        }
        int pre = 0;
        int cur = 1;
        int res = 0;
        for(int i = 2;i <= n;i++){
            res = pre + cur;
            pre = cur;
            cur = res;
        }
        return res;
    }

    public static int Fibonacc2(int n){
        if(n <= 1){
            return n;
        }else {
            return Fibonacc2(n - 1) + Fibonacc2(n-2);
        }
    }

    public static int Fibonacc3(int n){
        if(n <= 1){
            return n;
        }
        int[] fib = new int[n + 1];
        fib[0] = 0;
        fib[1] = 1;
        for(int i = 2;i <= n;i++){
            fib[i] = fib[i - 1] + fib[i-2];
//            System.out.println(i +":"+fib[i]);
        }
        return fib[n];

    }



}
